package heap

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	sort "gitee.com/ljfirst/algo-go-sdk/src/data_structure/sort/inner_sort"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/6/27 19:27
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 返回数组中最小的 k 个元素 -> 堆排法
 * */
type ReturnKMinByHeapSort struct {
}

func (m *ReturnKMinByHeapSort) ReturnKMin(array []int, k int) []int {
	if array == nil || len(array) < k {
		return nil
	}
	if len(array) == k {
		return array
	}
	ans := make([]int, 0)
	heap := &sort.HeapSort{
		IsSmallHeap: true, //调整为小顶堆
	}
	// 整堆
	for i := len(array)/2 - 1; i >= 0; i-- {
		heap.BuildHeapDown(array, i, len(array)-1)
	}
	for i := 0; i < k; i++ {
		heap.BuildHeapDown(array, 0, len(array)-1-i)
		ans = append(ans, array[0])
		array[0], array[len(array)-1-i] = array[len(array)-1-i], array[0]
	}
	return ans
}

func (m *ReturnKMinByHeapSort) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Sort, C.Heap},
		Desc: &C.Desc{
			Name:   "ReturnKMinByHeapSort",
			NameCn: "返回数组中最小的k个元素:堆排法",
			Example: map[int]string{
				1: "输入[1,3,2,4,5],K=2,最小的第2个元素是2",
			},
		},
	}
}
